package binary_search_tree

import (
	"fmt"
	"strings"
)

type tBinarySearchTree struct {
	comparator IComparator
	root       *tBinaryNode
	size       int
	version    uint64
}

func NewBinarySearchTree(comparator IComparator) IBinarySearchTree {
	return &tBinarySearchTree{
		comparator: comparator,
		root:       nil,
		size:       0,
		version:    0,
	}
}

func (me *tBinarySearchTree) Size() int {
	return me.size
}

func (me *tBinarySearchTree) IsEmpty() bool {
	return me.size <= 0
}

func (me *tBinarySearchTree) IsNotEmpty() bool {
	return !me.IsEmpty()
}

func (me *tBinarySearchTree) Push(value interface{}) {
	if me.IsEmpty() {
		me.root = me.append(value)
		return
	}

	for node := me.root; node != nil; {
		r := me.comparator.Compare(value, node.value)

		switch r {
		case EQUAL:
			return

		case LESS:
			if node.left == nil {
				node.LChild(me.append(value))
				return
			} else {
				node = node.left
			}
			break

		case GREATER:
			if node.right == nil {
				node.RChild(me.append(value))
				return
			} else {
				node = node.right
			}
			break
		}
	}
}

func (me *tBinarySearchTree) append(value interface{}) *tBinaryNode {
	me.size++
	me.version++
	return newBinaryNode(value)
}

func (me *tBinarySearchTree) Min() (bool, interface{}) {
	ok, node := me.getMinNode(me.root)
	if !ok {
		return false, nil
	}
	return true, node.value
}

func (me *tBinarySearchTree) Max() (bool, interface{}) {
	ok, node := me.getMaxNode(me.root)
	if !ok {
		return false, nil
	}
	return true, node.value
}


func (me *tBinarySearchTree) Has(value interface{}) bool {
	ok, _ := me.find(value)
	return ok
}

func (me *tBinarySearchTree) find(value interface{}) (ok bool, node *tBinaryNode) {
	if me.IsEmpty() {
		return false, nil
	}

	for node = me.root; node != nil; {
		r := me.comparator.Compare(value, node.value)

		switch r {
		case EQUAL:
			return true, node

		case LESS:
			if node.left == nil {
				return false, nil
			} else {
				node = node.left
			}
			break

		case GREATER:
			if node.right == nil {
				return false, nil
			} else {
				node = node.right
			}
			break
		}
	}

	return false, nil
}


func (me *tBinarySearchTree) getMinNode(from *tBinaryNode) (ok bool, left *tBinaryNode) {
	if from == nil {
		return false, nil
	}

	left = from.left
	if left == nil {
		return true, from
	}

	for {
		if left.left == nil {
			return true, left
		}

		left = left.left
	}
}

func (me *tBinarySearchTree) getMaxNode(from *tBinaryNode) (ok bool, right *tBinaryNode) {
	if from == nil {
		return false, nil
	}

	right = from.right
	if right == nil {
		return true, from
	}

	for {
		if right.right == nil {
			return true, right
		}

		right = right.right
	}
}

func (me *tBinarySearchTree) PopMin() (bool, interface{}) {
	ok, node := me.getMinNode(me.root)
	if !ok {
		return false, nil
	}
	value := node.value

	me.removeNode(node)

	me.size--
	me.version++

	return true, value
}


func (me *tBinarySearchTree) removeNode(node *tBinaryNode) {
	//var pv interface{} = "nil"
	//if node.parent != nil {
	//	pv = node.parent.value
	//}
	//fmt.Printf("removeNode %v.%v\n", pv, node.value)

	left := node.left
	right := node.right

	if node.parent == nil {
		switch node.childrenCount() {
		case 0:
			me.root = nil
			break

		case 1:
			if left != nil {
				me.root = left
				left.SetParent(nil)
			} else if right != nil {
				me.root = right
				right.SetParent(nil)
			}

		default:
			_, n := me.getMaxNode(left)
			if n == left {
				me.root = n
				n.SetParent(nil)
				n.RChild(right)

			} else {
				me.root.value = n.value
				me.removeNode(n)
			}
		}

	} else {
		parent := node.parent

		switch node.childrenCount() {
		case 0:
			if parent.left == node {
				parent.left = nil
			} else {
				parent.right = nil
			}
			break

		case 1:
			if left != nil {
				if parent.left == node {
					parent.LChild(left)
				} else {
					parent.RChild(left)
				}
			} else if right != nil {
				if parent.left == node {
					parent.LChild(right)
				} else {
					parent.RChild(right)
				}
			}

		default:
			_, n := me.getMaxNode(left)
			if n == left {
				if parent.left == node {
					parent.LChild(n)
				} else {
					parent.RChild(n)
				}
				n.RChild(right)

			} else {
				node.value = n.value
				me.removeNode(n)
			}
		}
	}
}

func (me *tBinarySearchTree) PopMax() (bool, interface{}) {
	ok, node := me.getMaxNode(me.root)
	if !ok {
		return false, nil
	}

	me.removeNode(node)

	me.size--
	me.version++

	return true, node.value
}

func (me *tBinarySearchTree) Remove(value interface{}) bool {
	ok, node := me.find(value)
	if !ok {
		return false
	}

	me.removeNode(node)

	me.size--
	me.version++

	return true
}

func (me *tBinarySearchTree) Clear() {
	if me.IsEmpty() {
		return
	}

	me.root = nil
	me.size = 0
	me.version++
}

func (me *tBinarySearchTree) Iterator() IIterator {
	return newBSTreeIterator(me)
}

func (me *tBinarySearchTree) String() string {
	queue := newVisitQeuue()
	queue.push(me.root)

	items := make([]string, 0)
	for ;queue.more(); {
		ok, node := queue.poll()
		if ok {
			queue.push(node.left)
			queue.push(node.right)

			var lv interface{} = "n"
			if node.left != nil {
				lv = node.left.value
			}
			var rv interface{} = "n"
			if node.right != nil {
				rv = node.right.value
			}
			items = append(items, fmt.Sprintf("%v(%v,%v)", node.value, lv,rv))

		} else {
			break
		}
	}

	r := "nil"
	if me.root != nil {
		r = fmt.Sprintf("%v", me.root.value)
	}

	if len(items) > 0 {
		return fmt.Sprintf("r=%v,s=%v,v=%v %s", r, me.size, me.version, strings.Join(items, ","))
	} else {
		return fmt.Sprintf("r=%v,s=%v,v=%v", r, me.size, me.version)
	}
}